/**
 * 234. 回文链表
 * https://leetcode-cn.com/problems/palindrome-linked-list/
 */
const { createListNode } = require('../../libs/public');

/**
 * @param {ListNode} head
 * @return {boolean}
 */
function isPalindrome(head) {
  let length = 0;
  let node = head;
  while (node) {
    length += 1;
    node = node.next;
  }
  if (length <= 1) return true;
  const half = Math.floor(length / 2);
  node = head;
  let pre = null;
  let next;
  for (let i = 0; i < half; i += 1) {
    next = node.next;
    node.next = pre;
    pre = node;
    node = next;
  }
  let node1 = pre;
  let node2 = next;
  if (length % 2 === 1) {
    node2 = node2.next;
  }
  while (node1 && node2) {
    if (node1.val !== node2.val) {
      return false;
    }
    node1 = node1.next;
    node2 = node2.next;
  }
  return true;
}

console.log(isPalindrome(createListNode([1, 2, 2, 1])) === true);
console.log(isPalindrome(createListNode([1, 2])) === false);
console.log(isPalindrome(createListNode([1, 2, 1])) === true);
console.log(isPalindrome(createListNode([1])) === true);
